import random
import math

def euclidean_distance(point1, point2):
    if len(point1) != len(point2):
        raise ValueError("点的维度必须相同")
    squared_distance = 0
    for i in range(len(point1)):
        squared_distance += (point1[i] - point2[i]) ** 2
    return math.sqrt(squared_distance)

def assign_cluster(x, centroids):
    min_distance = float('inf')
    closest_centroid = 0
    for i, centroid in enumerate(centroids):
        distance = euclidean_distance(x, centroid)
        if distance < min_distance:
            min_distance = distance
            closest_centroid = i
    return closest_centroid

def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    centroids = random.sample(data, k)
    clusters = [0] * len(data)
    iteration = 0
    centroid_movement = float('inf')
    while iteration < max_iterations and centroid_movement > epsilon:
        for i, point in enumerate(data):
            clusters[i] = assign_cluster(point, centroids)
        new_centroids = []

        for cluster_idx in range(k):
            cluster_points = [data[i] for i in range(len(data)) if clusters[i] == cluster_idx]

            if len(cluster_points) == 0:
                new_centroids.append(random.choice(data))
            else:
                dimension = len(cluster_points[0])
                new_centroid = [0] * dimension
                for point in cluster_points:
                    for d in range(dimension):
                        new_centroid[d] += point[d]
                for d in range(dimension):
                    new_centroid[d] /= len(cluster_points)
                new_centroids.append(new_centroid)
        centroid_movement = 0
        for i in range(k):
            centroid_movement += euclidean_distance(centroids[i], new_centroids[i])
        centroid_movement /= k
        centroids = new_centroids
        iteration += 1
        print(f"迭代 {iteration}: 质心平均移动距离 = {centroid_movement:.6f}")
    print(f"聚类完成，共迭代 {iteration} 次")
    return centroids, clusters
def calculate_sse(data, clusters, centroids):
    sse = 0
    for i, point in enumerate(data):
        cluster_idx = clusters[i]
        sse += euclidean_distance(point, centroids[cluster_idx]) ** 2
    return sse